#include <iostream>
#include <string>

int const mo = 100000007;
int const maxn = 100002;

long long f[maxn][10];
int next[10][10];
int n;
std::string s;

std::string change(std::string s)
{
	int p = 0;
	for (; p < (int)s.size(); p++)
		if (s[p] == '0') break;
	if (p == (int)s.size()) return s;
	int p1 = 0;
	for (; p1 < p; p1++)
		if (s[p1] != '1') break;

	if (p1 == p) return std::string((int)s.size() - 1, '9');
	s[p1] -= 1;
	for (int i = p1 + 1; i < (int)s.size(); i++)
		s[i] = '9';
	return s;
}

int main()
{
	next[1][0] = 1; next[1][1] = 1;
	next[2][0] = 2; next[2][1] = 1; next[2][2] = 2;
	next[3][0] = 2; next[3][1] = 1; next[3][2] = 3;
	next[4][0] = 3; next[4][1] = 1; next[4][2] = 2; next[4][3] = 4;
	next[5][0] = 2; next[5][1] = 1; next[5][2] = 5;
	next[6][0] = 4; next[6][1] = 1; next[6][2] = 2; next[6][3] = 3; next[6][4] = 6;
	next[7][0] = 2; next[7][1] = 1; next[7][2] = 7;
	next[8][0] = 4; next[8][1] = 1; next[8][2] = 2; next[8][3] = 4; next[8][4] = 8;
	next[9][0] = 3; next[9][1] = 1; next[9][2] = 3; next[9][3] = 9;

	std::string a{"11"};
	std::string b{"11"};
	std::cout << (a == b) << '\n';
	int T;
	std::cin >> T;
	while (T--) {
		std::cin >> s;
		s = change(s);
		int len = s.size();
		for (int i = 0; i <= len; i++)
			for (int j = 0; j <= 9; j++) f[i][j] = 0;

		for (int j = 1; j <= 9; j++) f[1][j] = 1;
		for (int i = 2; i <= len; i++)
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= next[j][0]; k++)
					f[i][j] = (f[i][j] + f[i-1][next[j][k]]) % mo;
			}

		/*
		for (int i = 1; i <= len; i++) {
			for (int j = 1; j <= 9; j++) std::cout << f[i][j] << ' ';
			std::cout << '\n';
		}
		*/
		long long ans = 0;
		for (int i = 1; i < s[0] - '0'; i++) ans = (ans + f[len][i]) % mo;
		if (len == 1) ans++;
		for (int j = len-1; j >= 1; j--)
			for (int i = 1; i <= 9; i++) ans = (ans + f[j][i]) % mo;
		int high = s[0] - '0';
		for (int i = 1; i < len; i++) {
			for (int j = 1; j <= next[high][0] && (next[high][j] < s[i] - '0'
						|| (i == len-1 && next[high][j] == s[i]- '0'));
						j++)
				ans = (ans + f[len - i][j]) % mo;
			high = s[i] - '0';
		}
		std::cout << ans % mo <<'\n';
	}
}

